slope trick 1

요새 slope trick문제가 자주 보여서 각잡고 공부해봤다.

사전지식

Convex함수는 +,-,*,min 연산에 대해 닫혀있다.(Concave함수는 +,-,*,max)

많은 문제들이 최소화를 묻기 때문에 이 글에서는 Concave기준으로 설명한다.

기능

정수기울기를 가지는 일차함수로 이루어진 Concave함수들에 대한 다양한 연산을 효율적으로 할 수 있다

유형

$f(i,x)=\min\limits_{y \leq x+b}(f(i-1,y))+STF$ 형태
$f(i,x)=\min\limits_{x \leq y \leq x+b}(f(i-1,y))+STF$ 형태
$f(i,x)=\min\limits_{y \leq x+b}(f(i-1,y)+|y-k|)$ 형태
$f(i,x)=\min(f(i-1,x),f(i-1,x+1)+p)$ 형태 (SlopeTrick2 에서 다룬다)

slopetrick-able function을 STF라고 썼다.

아이디어

위의 점화식들을 보자. f(i,?)가 f(i-1,?)에만 의존하기 때문에 f(i-1,?)에 대한 정보를 알고있다면 f(i,?)를 구할 수 있다.

또한 점화식이 나타내는 그래프의 개형을 떠올려야 충분한 이해를 할 수 있는데, 그림으로 설명된 글은 문서 마지막의 참고자료문단을 참고하자. 결론적으로, 점화식으로 만들어지는 그래프 또한 slopetrick-able concave 함수가 된다!

유형1,2: concave함수 자체는 min연산에 대해 닫혀있지 않다(max에 닫혀있다). 그러나 "임의의 concave함수"가 아니라 f(i-1,?)에 대한 연속된 평행이동들에 대한 min(f(i-1,?))은 최솟값을 기준으로 left hull과 righthull의 간격이 벌어지는 형태가 되며, 이는 다시 slopetrick-able concave함수이므로 닫혀있음을 알 수 있다.

유형3: 최솟값 부분이 그냥 넓어지는게 아니라 |y-k|형태로 움직이며 누적min되므로 조금 귀찮다. APIO2016 Fireworks가 이런 형태. 최솟값이 움직이는 모양대로 그래프가 확장된다.

concave함수를 표현할때 직선자체를 저장하지 말고, 기울기가 변하는(NOTE: [기울기=미분]이고, [기울기의 변화=미분의 미분]이므로 이계도함수를 저장한다는 관점으로 보면 이해가 쉬울듯) x좌표만 저장해보자. 그래도 STF함수를 표현하는데 문제가 없다는 것이 이해되는가? 기울기가 k만큼 증가하면 해당x좌표를 k번 저장해야 하므로 multiset 개념으로 이해하자.

또한 유형2의 최솟값의 구간이 넓어지는 연산(cumulative min)의 효율성을 위해 최솟값 기준으로 left hull과 right hull 2개를 관리하자

이제 이렇게 표현한 볼록껍질은 다양한 연산을 효율적으로 할 수 있다.

O(1) shift (bias조정) -> O(1) cumulative min 가능
O(1) prefix decrease (왼쪽직선 기울기 -1)
O(1) suffix increase (오른쪽직선 기울기 +1)
O(NlogN) 두 볼록껍질의 덧셈 (합집합)

(아마도?) 모든 slope trickable function은 위 연산의 조합으로 표현할 수 있다. 그러므로 저 연산들만 잘 구현해두면 두고두고 써먹을 수 있다.

다이아 루비 복사버그

코드

Left Hull 기준으로, pf_dec은 pq.push(x)이고, sf_inc(x)는 x가 최소값위치보다 안쪽일때 그 거리만큼 y좌표 증가하고 pop,push(x)이다. 구하는 답(최소값)은 이 연산에서 y좌표 증가값 누적한 것이다. Right Hull은 Left Hull에서 x좌표 반전해서 잘 거꾸로 관리해주면 된다.

유형1의 경우 최솟값 오른쪽은 항상 기울기가 0이 되기때문에, left hull만 관리해도 된다.

//NOTE: f(x)=min{f(x+i),i<a}+|x-k|+m -> pf(k)sf(k)ab(-a,m)
//NOTE: sf_inc에 답구하는게 들어있어서, 반드시 한 연산에 대해 pf_dec->sf_inc순서로 호출
struct LeftHull{
	void pf_dec(int x){pq.empl(x-bias);}//x이하의 기울기들 -1
	int sf_inc(int x){//x이상의 기울기들 +1, pop된 원소 반환(Right Hull관리에 사용됨)
		if(pq.empty() or argmin()<=x)return x;
		ans+=argmin()-x;//이 경우 최솟값이 증가함
		pq.empl(x-bias);//x 이하 -1
		int r=argmin();pq.pop();//전체 +1
		return r;
	}
	void add_bias(int x,int y){bias+=x;ans+=y;}//그래프 x축 평행이동
	int minval(){return ans;}//최소값
	int argmin(){return pq.empty()?-inf<int>():pq.top()+bias;}//최소값 x좌표

	void operator+=(LeftHull& a){
		ans+=a.ans;
		while(sz(a.pq))pf_dec(a.argmin()), a.pq.pop();
	}
	int size()const{return sz(pq);}
	
// private:
	PQMax<int> pq;
	int ans=0,bias=0;
};

//NOTE: f(x)=min{f(x+i),a<i<b}+|x-k|+m -> pf(k)sf(k)ab(-a,b,m)
struct SlopeTrick{
	void pf_dec(int x){l.pf_dec(-r.sf_inc(-x));}
	void sf_inc(int x){r.pf_dec(-l.sf_inc(x));}
	void add_bias(int lx,int rx,int y){l.add_bias(lx,0),r.add_bias(-rx,0),ans+=y;}
	int minval(){return ans+l.minval()+r.minval();}
	pint argmin(){return {l.argmin(),-r.argmin()};}
	void operator+=(SlopeTrick& a){
		//그냥 Left Right 각각 +=하면 안되는 이유: 최솟값이 증가하며, 최소구간이 꼬일수 있음.
		ans+=a.ans;
		while(sz(a.l.pq))
			pf_dec(a.l.argmin()),a.l.pq.pop();
		l.ans+=a.l.ans;
		while(sz(a.r.pq))
			sf_inc(-a.r.argmin()),a.r.pq.pop();
		r.ans+=a.r.ans;
	}
	int size()const{return l.size()+r.size();}
// private:
	LeftHull l,r;
	int ans=0;
};

NOTE: 업뎃하는 slope가 너무 크면 PQ대신 map으로 표현해야할수도 있다. 코드가 좀 더 더럽고 느려진다. https://www.codechef.com/OCT16/problems/TREEBAL 이게 그렇다는듯. BOJ3685김강산 도 매우 큰 슬로프 업데이트를 추가해 풀 수 있음.

관련문제

유형1

CF371C) Sonya and Problem Wihtout a Legend
BOJ13323) BOJ수열1
BOJ13324) BOJ수열2
ARC123D) Inc, Dec - Decomposition
BOJ18720) Bookface
관찰&정리+non-negative 조건처리

유형2

NOI18 Safety

#include "core/base.h"
#include "core/fastio.h"
#define endl '\n'
#include "dp/slope.h"
signed main(){
	READ(int,n,h);
	auto a=cin.toks(n);
	SlopeTrick st;
	for(int i=0;i<n;i++){
		st.pf_dec(a[i]);
		st.sf_inc(a[i]);
		st.add_bias(-h,h,0);
	}
	cout<<st.getmin()<<endl;
}

유형3

APIO2016 Fireworks
$f_i(x)$=(서브트리i+부모간선)이 x시간에 터지도록할때 최소비용

$f_i(x)=\min\limits_{0 \leq y \leq x}(\sum\limits_{j=child}f_j(x-y)+|c_i-y|)$

$f_i(x)=|c_i-x|$ (i가 리프노드일때)

y가 x보다 크면 무조건 최적이 아니기 때문에 2번 수식의 y<=x 조건 없이 풀어도 된다는듯.

[개형분석]

표기의 편의를 위해 $f_{sum} = \sum\limits_{j=child}f_j$라고 두자. 이제 y=0부터 올라가며 살펴보자.

y=0 -> $f_{sum}(x)+|c_i|$

y=1 -> $f_{sum}(x-1)+|c_i-1|$

...기울기-1로 감소...

y=c_i -> $f_{sum}(x-c_i)+|0|$

y=c_i+1 -> $f_{sum}(x-c_i-1)+|1|$

...기울기1로 증가...

위와 같은 패턴(최솟값 오른쪽으로 -1기울기로 감소했다가 c_i만큼 움직인 이후에는 기울기1로 증가하는 형태)을 발견할 수 있다. 이제 저걸 잘(...)구현하면 된다.

미분류(아직안품)(공부 & 작성 중이라 대충만 적음)

위에서 풀었던것들은 $ans=\min\limits_{0 \leq x \lt n(f(n-1,x))}$형태라 최종 그래프의 min값 출력하면 됬지만 $ans=f(n,0)$ 이런경우 그래프의 실제값 구해야할수도 있을듯.

또 식만봐서는 이게 볼록인지 감이 잘 안오는데 Min cost flow로 풀수 있으니 볼록이라거나, 기울기증감위치가 아니라 각 x좌표에 대해 이전값과의 차이를 저장한다거나 하는 문제도 있던데 아직 공부중이다.

seerc 2020 A번 Archeologists: 이 문제의 에디토리얼은 slope trick, convexity, flow, dual의 이론적인 배경과 그 관계에 대해 설명해주고 있다. 관심있으면 읽어보자. https://drive.google.com/file/d/13WApgof_TR5W-pokndhBQiqdny9wggVw/view
potatoes and fertilizers KOI소방차
Farm of Monsters 조건을 정리하다보면 prefix sum의 뭔가로 slope trick을 한다는듯 https://drive.google.com/file/d/1PUz2-MKpAsX0YO-q4fY93wk5caN0Gvmu/view

Slope Trick을 바라보는 여러가지 관점

dp점화식의 기하적 관점: 위에서 설명한것
Greedy: https://codeforces.com/blog/entry/91725 save해놓고 나중에 사용한다는 느낌인듯. 주유소문제 확장판? 이해는되는데 NOISafety설명부터는 뭔소린지 복잡해져서 그냥 슬로프트릭 개념을 이해하는게 나을거같다.
Min Cost Flow: seerc 2020 A번 에디토리얼

뭐 사실 Min Cost Flow가 요리조리 제한시킨 그래프형태에서 자주 그리디가 가능하다는건 알려져 있으니 2,3번은 근본적으로 비슷하다.(LP로 통합하여 볼수 있음)

참고자료

https://gratus907.github.io/algorithms/BOJ19693/

https://codeforces.com/blog/entry/77298

https://usaco.guide/adv/slope?lang=cpp

https://jwvg0425-ps.tistory.com/98

https://atcoder.jp/contests/arc123/editorial/2318

https://codeforces.com/blog/entry/47821

https://koosaga.com/243

https://koosaga.com/113